package SelectSort;/*
 *
 *@author:    Xavier
 *@data:      2023 - 08 - 27
 *@time:      17:20
 *
 */

import java.util.Arrays;

//堆排序
//PS：指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。
// 它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

/*
* 时间复杂度：O(N*logN) 对数据不敏感 不管有序无序都是这个
* 空间复杂度：O(1)
* 稳定性；不稳定
* */
public class HeapSort {
    public static void heapSort(int[] arr) {
        createBigHeap(arr);
        int end = arr.length - 1;
        while (end > 0) {
            swap(arr,end,0);
            siftDown(arr,0,end);
            end--;
        }
    }

    private static void createBigHeap(int[] arr) {
        for (int i = (arr.length -1 -1) / 2; i >= 0; i--) {
            siftDown(arr,i,arr.length);
        }
    }

    private static void siftDown(int[] arr,int parent, int len) {
        int child = 2*parent + 1;
        while (child < len) {
            if (child+1 < len && arr[child] < arr[child+1]) {
                child++;
            }
            if (arr[child] > arr[parent]) {
                swap(arr, child, parent);
                parent = child;
                child = 2*parent + 1;
            }else {
                break;
            }
        }
    }

    private static void swap(int[] arr, int i , int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr1 = {2,8,7,3,9,5,9,0,0,2};
        int[] arr = {10,2,8,7,3,9,5,9,0,0,2};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
